package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/">填充每个节点的下一个右侧节点指针 II(Populating Next Right Pointers in Each Node II)</a>
 * <p>给定一个二叉树：
 * <pre>
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * </pre>
 * </p>
 * <p>
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
 * 初始状态下，所有 next 指针都被设置为 NULL 。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre><a href='https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/'>查看示例</a></pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *      <li>树中的节点数在范围 [0, 6000] 内</li>
 *      <li>-100 <= Node.val <= 100</li>
 *     </ul>
 * </p>
 * <b>进阶：</b>
 * <li>你只能使用常量级额外空间。</li>
 * <li>使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。</li>
 *
 * @author c2b
 * @see LC0116PopulatingNextRightPointersInEachNode_I_M 填充每个节点的下一个右侧节点指针 I
 * @see LC0117PopulatingNextRightPointersInEachNode_II_M 填充每个节点的下一个右侧节点指针 II
 * @since 2025/2/8 14:40
 */
public class LC0117PopulatingNextRightPointersInEachNode_II_M {
    static class Solution {
        public Node connect(Node root) {
            // 为每一个创建一个虚拟头节点，通过next指针将这一行的所有节点串起来。列斯与链表
            //return connect1(root);
            // 使用一个变量去记录下一层的最左节点
            return connect2(root);
        }

        private Node connect2(Node root) {
            if (root == null) {
                return null;
            }
            Node currLevelLeftmostNode = root;
            while (currLevelLeftmostNode != null) {
                Node currNode = currLevelLeftmostNode;
                // nextLevelLeftmostNode 用于记录下一层最左侧的节点
                Node nextLevelLeftmostNode = null;
                while (currNode != null) {
                    // 如果 currNode 有左子节点，改变当前节点左子节点的`next`指针，并更新nextLevelLeftmostNode
                    if (currNode.left != null) {
                        currNode.left.next = currNode.right != null ? currNode.right : getNextNode(currNode);
                        // 更新 nextLevelLeftmostNode
                        if (nextLevelLeftmostNode == null) {
                            nextLevelLeftmostNode = currNode.left;
                        }
                    }
                    // 如果 currNode 有右子节点，改变当前节点右子节点的`next`指针，并更新nextLevelLeftmostNode
                    if (currNode.right != null) {
                        currNode.right.next = getNextNode(currNode);
                        // 更新 nextLevelLeftmostNode
                        if (nextLevelLeftmostNode == null) {
                            nextLevelLeftmostNode = currNode.right;
                        }
                    }
                    currNode = currNode.next;
                }
                currLevelLeftmostNode = nextLevelLeftmostNode;
            }
            return root;
        }

        private Node getNextNode(Node currNode) {
            while (currNode.next != null) {
                if (currNode.next.left != null) {
                    return currNode.next.left;
                }
                if (currNode.next.right != null) {
                    return currNode.next.right;
                }
                currNode = currNode.next;
            }
            return null;
        }

        /**
         * 不使用额外空间
         */
        private Node connect1(Node root) {
            if (root == null) {
                return null;
            }
            // 当前层最左节点，用于进入下一层
            Node currNode = root;
            while (currNode != null) {
                // 创建一个哑节点。通过遍历当前层，把下一层的节点串起来
                Node dummyNode = new Node(-1);
                Node tempNode = dummyNode;
                while (currNode != null) {
                    if (currNode.left != null) {
                        tempNode.next = currNode.left;
                        tempNode = tempNode.next;
                    }
                    if (currNode.right != null) {
                        tempNode.next = currNode.right;
                        tempNode = tempNode.next;
                    }
                    // 继续访问当前行的下一个节点
                    currNode = currNode.next;
                }
                // 进入下一层
                currNode = dummyNode.next;
            }

            return root;
        }

        ///**
        // * 使用额外空间：队列。层序遍历
        // */
        //public Node connect(Node root) {
        //    if (root == null) {
        //        return null;
        //    }
        //    Queue<Node> helper = new LinkedList<>();
        //    helper.offer(root);
        //    while (!helper.isEmpty()) {
        //        int currLevelNodeSize = helper.size();
        //        Node prevNode = null;
        //        for (int i = 0; i < currLevelNodeSize; i++) {
        //            Node currNode = helper.poll();
        //            currNode.next = prevNode;
        //            prevNode = currNode;
        //            if (currNode.right != null) {
        //                helper.offer(currNode.right);
        //            }
        //            if (currNode.left != null) {
        //                helper.offer(currNode.left);
        //            }
        //        }
        //    }
        //    return root;
        //}
    }

    private static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.right = new Node(7);
        //node.right.right = new Node(6);
        //node.left.left.left = new Node(7);
        //node.right.right.right = new Node(8);
        //Node node = new Node(1);
        //node.right = new Node(-9);
        //node.right.right = new Node(8);
        //node.right.right.left = new Node(4);
        //node.right.right.right = new Node(-3);
        //node.right.right.right.left = new Node(-3);
        //node.right.right.right.left.left = new Node(-6);
        //node.right.right.right.left.left.right = new Node(-6);
        //node.right.right.right.left.left.right.left = new Node(-4);
        //node.right.right.right.left.left.right.right = new Node(-9);
        //node.right.right.right.left.left.right.right.left = new Node(6);
        Node connect = new Solution().connect(node);
    }
}
